Heretofore, it is known that the convolutional encoding and error correction technologies are applied frequently in the receiving ends of the wireless communications.
The processes include the steps of decoding of the encoded signals and converting the signals into readable data. Viterbi decoders are a kind of popular convolutional decoder, calculating the received signals based on the built-in parameters and tracing possible routes to restore the original data.
Referring to FIG. 1, a Viterbi decoder includes three major portions: a branch metric generation unit (BMU), a path metric uploading unit (PMU) and a survivor memory management unit (SMU). The BMU calculates and generates a branch metric 101 based on input signals IN. The PMU carries out a comparison and generates new branch route 103. The SMU decodes and outputs correct data OUT through the branch route 103.
The branch metric 101 is the tracks during encoding. FIG. 2 illustrates a trellis diagram of a convolutional encoder. Column 201 shows that a branch metric with a length of 8 can have 28−1=128 states (0˜127). Row 203 indicates the input bits (Bit0˜BitN) of the encoder. State 205 indicates the current status of the encoder. It may transfer to a next state in the direction of Arrow 207. Every state has two transferable states decided by Row 203. The Viterbi decoder restores the data of Row 203 by means of the branch metric 101.
Since every state comes from two previous states, there are two repeated statuses. The shape of the bold lines in FIG. 2 looks like a butterfly. The branch metric 101 basically consists of many butterfly-like patterns. FIG. 3 shows a butterfly pattern 209. Either State 301 or State 303 is the current state of the encoder. States 305 and 307 are next possible states. Both States 301 and 303 might transfer to States 305 and 307. The current input to the encoder decides the next state going to be State 305 or state 307. For example, if the current state is Sate 301, it follows the transition direction 302 toward State 305 when the input is 0, and, otherwise, it follows transition direction 304 toward State 307 when the input is 1.
FIG. 4 is a block diagram of BMU. As shown in FIG. 4, BMU includes two circuitries: one is a branch metric generator BMG and the other is a branch metric calculator BMC. BMG includes two outputs, ref_bit_0 and ref_bit_1, to provide every route's ideal data values. BMC calculates the difference between received signals, rec_bit_0 and rec_bit_1, and ideal data values, ref bit_0 and ref bit_1, and then transmits the difference toward PMU in FIG. 1. During data transmission, one usually divides data into positive and negative portions, e.g. a 7-bit data can be divided into (1˜64) and (−1˜−64). When the outputs, ref_bit_0 and ref_bit_1, of BMG are all 0, it means the received signals, rec_bit_0 and rec_bit_1, should be within (1˜64). When the outputs, ref_bit_0 and ref_bit_1, of BMG are all 1, it means the received signals, rec_bit_0 and rec_bit_1, should be within (−1˜−64). For example, if {rec_bit_0, rec_bit_1}={24, −55} and {ref_bit_0, ref_bit—1}={0,0}, one can realize that rec_bit_0=24 is correct but rec_bit_1=−55 is wrong. Therefore, the outputs of BMU modify {rec_bit_0, rec_bit_1}={24, −55} to {out_bit _0, out_bit_1}={0,55}. After that, one chooses a shorter route as the correct decoding route.
In order to determine if the received data is correct, the prior art decoders store ideal data values in BMG in advance to compare with the received data. However, the method of the prior art needs at least an adder and a memory built in BMG, and moreover needs a circuit to generate addresses pointing to the memory. Such arrangement not only limits the speed of decoders but also increases layout area of the circuit. Besides, BMG is designed to be able to generate many sets of branch metrics for different systems. FIG. 5 illustrates a ½ rate BMG of the prior art, which decides a branch metric by an input sel_in. Such structure requires several multiplexers to select the branch metric and, as mentioned above, enlarges its physical size that results in higher manufacturing cost.